Vasilis Syrgkanis
Game-theoretic models relevant for computer science applications usually feature a large number of players with predictable structural properties. The goal of this talk is to develop an analytical framework for bounding the price of anarchy in such models.
Our framework is based on a novel extension of smoothness, a standard technique for developing price-of-anarchy bounds in fixed games, to a sequence of games. We first define an approximate utility -- one that a delusional player might imagine he faces. We prove that this utility well-approximates the actual utility under realistic structural assumptions regarding market size and noise. We then show that this approximate utility is smooth with respect to the actual game.
We demonstrate the wide applicability of our framework through instantiations for several well-studied models, including simultaneous single-item auctions, greedy combinatorial auctions, and routing games. In all cases, we identify conditions under which the POA of large games is much better than that of worst-case instances. Our results also give new senses in which simple auctions can perform almost as well as optimal ones in realistic settings.
Based on joint work with Michal Feldman, Nicole Immorlica, Brendan Lucier and Tim Roughgarden.